Wednesday Code and Notes (Week 4)

1. Java code
2. Notes

1 Java code

1.1 Dining philosophers, first attempt

import java.util.concurrent.Semaphore;

class Philosopher extends Thread {
    String name;
    Semaphore left_fork;
    Semaphore right_fork;

    Philosopher(String name, Semaphore left_fork, Semaphore right_fork) {
        this.name = name;
        this.left_fork = left_fork;
        this.right_fork = right_fork;        
    }

    public void run () {
        while(true) {
            System.out.println(name + " thinks...");
            try {
                Thread.sleep(150);
            }
            catch(InterruptedException e) {
            }

            left_fork.acquireUninterruptibly();
            System.out.println(name + " grabbed a fork...");
            try {
                Thread.sleep(150);
            }
            catch(InterruptedException e) {
            }
            right_fork.acquireUninterruptibly();
            System.out.println(name + " grabbed another fork...");            
            System.out.println(name + " eating...");
            try {
                Thread.sleep(150);
            }
            catch(InterruptedException e) {
            }
            System.out.println(name + " releases forks...");
            left_fork.release();
            right_fork.release();
        }
    }
}

public class Dinphil {
    public static void main(String[] args) {
        // we want binary semaphores that have 1 free ticket initially
        // we don't care about liveness here, only deadlock
        Semaphore fork1 = new Semaphore(1,false);
        Semaphore fork2 = new Semaphore(1,false);
        Semaphore fork3 = new Semaphore(1,false);                
        Thread t1 = new Philosopher("Hegel",fork1,fork2);
        Thread t2 = new Philosopher("Plato",fork2,fork3);
        Thread t3 = new Philosopher("Averroes",fork3,fork1);

        t1.start();
        t2.start();
        t3.start();                
    }
}

/* We're deadlocked :(
   Suggestion:
   - make "grab both forks" a critical section
     with another semaphore, shared between
     everybody
   - ordering the forks
     In the system as a whole, we'll have
         n   locks  (or semaphores)
     each process requires some subset of the
     locks

     Globally order all the locks
     Total order:
        fork1 < fork2 < fork3
     Enforce discipline:
        everybody needs to claim the "smallest"
        lock first

     If everybody claims locks in an order
     consistent w/ the total order,
     deadlock is impossible.

     If P is stuck, that means somebody is
     hogging a higher lock.
     But the process hogging the *highest* lock
     can't be stuck.
 */

1.2 Dining philosophers, second attempt

This solution fixes the deadlock issue by enforcing a total order on locks.

import java.util.concurrent.Semaphore;

class Philosopher extends Thread {
    String name;
    Semaphore left_fork;
    Semaphore right_fork;

    Philosopher(String name, Semaphore left_fork, Semaphore right_fork) {
        this.name = name;
        this.left_fork = left_fork;
        this.right_fork = right_fork;        
    }

    public void run () {
        while(true) {
            System.out.println(name + " thinks...");
            try {
                Thread.sleep(150);
            }
            catch(InterruptedException e) {
            }

            left_fork.acquireUninterruptibly();
            System.out.println(name + " grabbed a fork...");
            try {
                Thread.sleep(150);
            }
            catch(InterruptedException e) {
            }
            right_fork.acquireUninterruptibly();
            System.out.println(name + " grabbed another fork...");            
            System.out.println(name + " eating...");
            try {
                Thread.sleep(150);
            }
            catch(InterruptedException e) {
            }
            System.out.println(name + " releases forks...");
            left_fork.release();
            right_fork.release();
        }
    }
}

public class Dinphil2 {
    public static void main(String[] args) {
        // we want binary semaphores that have 1 free ticket initially
        // we don't care about liveness here, only deadlock
        Semaphore fork1 = new Semaphore(1,false);
        Semaphore fork2 = new Semaphore(1,false);
        Semaphore fork3 = new Semaphore(1,false);
        // fork1 < fork2 < fork3
        Thread t1 = new Philosopher("Hegel",fork1,fork2);
        Thread t2 = new Philosopher("Plato",fork2,fork3);
        Thread t3 = new Philosopher("Averroes",fork1,fork3);

        t1.start();
        t2.start();
        t3.start();                
    }
}

1.3 Rendezvous, first attempt

import java.util.concurrent.Semaphore;

class RendezvousThread extends Thread {
    String name;

    public RendezvousThread(String name) {
        this.name = name;
    }

    public void run() {
        System.out.println(name + " first statement");
        System.out.println(name + " second statement");        
    }
}

public class Rendezvous {
    public static void main(String[] args) {
        Thread t1 = new RendezvousThread("Bertram");
        Thread t2 = new RendezvousThread("Agatha");

        t1.start();
        t2.start();
    }
}

1.4 Rendezvous, second attempt

import java.util.concurrent.Semaphore;

class RendezvousThread extends Thread {
    String name;
    Semaphore s1;
    Semaphore s2;

    public RendezvousThread(String name, Semaphore s1, Semaphore s2) {
        this.name = name;
        this.s1 = s1;
        this.s2 = s2;
    }

    public void run() {
        System.out.println(name + " first statement");
        // here, we want to: unblock the other proc
        // wait until the other proc unblocks us
        s1.release();
        s2.acquireUninterruptibly();
        System.out.println(name + " second statement");        
    }
}

public class Rendezvous2 {
    public static void main(String[] args) {
        Semaphore s1 = new Semaphore(0);
        Semaphore s2 = new Semaphore(0);
        Thread t1 = new RendezvousThread("Bertram",s1,s2);
        Thread t2 = new RendezvousThread("Agatha",s2,s1);

        t1.start(); // start means
                    // execute run() in a new thread
        t2.start();
    }
}

1.5 Rendezvous, attempt 3

Here's a hack we can do to achieve the same thing with one Java semaphore, because of the oddity that we can have initially negative number of permits.

import java.util.concurrent.Semaphore;

class RendezvousThread extends Thread {
    String name;
    Semaphore s1;

    public RendezvousThread(String name, Semaphore s1) {
        this.name = name;
        this.s1 = s1;
    }

    public void run() {
        System.out.println(name + " first statement");
        // here, we want to: unblock the other proc
        // wait until the other proc unblocks us
        s1.release();
        s1.acquireUninterruptibly();
        System.out.println(name + " second statement");
        s1.release();
    }
}

public class Rendezvous3 {
    public static void main(String[] args) {
        Semaphore s1 = new Semaphore(-1);
        Thread t1 = new RendezvousThread("Bertram",s1);
        Thread t2 = new RendezvousThread("Agatha",s1);

        t1.start(); // start means
                    // execute run() in a new thread
        t2.start();
    }
}

2 Notes

Locks:
  - lock()  acquire()      --- pre-protocol
    unlock() release()     --- post-protocol

  Locks: only one process can claim the lock at one time.

Semaphores:
  - multiple process can pass through a semaphore at the same time.

  Binary semaphores: (v,L)
   - v number of free process slots, free tickets
   - L processes on waiting list

  For binary semaphores, v is always either 0 or 1.

  A lock is a special case of a semaphore, namely a binary semaphore.

            wait        signal
acronyms    P           V
dutch       passering   vrijgaven
java        acquire     release


Difference:
- when we signal, we unblocke someone from the waiting set.
  But: who gets unblocked? And to where do they get unblocked?

busy-wait semaphores
aka very weak semaphores
- You're unblocked to the state *before* the wait.
  You have to try another wait.
  This means you can be preempted by people who weren't
  on the waiting list when the signal came.
- Who gets unblocked? Any member of L.

weak semaphores
- When a signal happens, one process, any process, is unblocked.
- You're released to the state *after* the wait.
  That is: you're released into the "critical section",
   and don't have to retry the wait.

strong semaphores
- Processes are released in FIFO order.
- You're released to the state *after* the wait.
  That is: you're released into the "critical section",
   and don't have to retry the wait.


Q: What impact does weak vs. busy-wait have on eventual entry?
   (for 2 processes)

    Busy-wait (aka very weak) doesn't guarantee eventual entry.
    Weak semaphores do guarantee eventual entry.

Q: What about for 3 or more procs?

    Weak semaphores don't guarantee eventual entry.
    If you're unlucky, every signal happens when you're sharing the
     waiting room with someone else, who push ahead.
Q: but what about under weak fairness?
    Still no :(

    Weak fairness guarantees that if an action is *always* enabled,
    then it will eventually happen.
    (If a process is always not blocked, it will eventually
     make progress).
    But: you're not *always* unblocked.
    You're *always eventually* unblocked.

    Suppose p1 is on the waiting list.
      p2 and p3 are forever taking turns entering the CS.
    p1 will:
    - sit on the wait list (be blocked)
    - be unblocked whenever anyone's about to execute the pre-protocol.
      (unblocked: you could possibly be chosen to go ahead)
    - in the next state, you're blocked again.
    - repeat ad infinitum

Q: what about under strong fairness?
A: Yes, strong fairness is enough (see above).


(1) v = 1 + #signal(S) - #wait(S)
(2) v ≥ 0
(3) #CS = #wait(S) - #signal(S)

Substitute (1) into (2)

1 + #signal(S) - #wait(S) ≥ 0
(add and subtract on both sides)
1 ≥ #wait(s) - #signal(S) = #CS

#CS ≤ 1